package com.yeung.exam;

public class 携程n维数组的最大子数组 {

    public static void main(String[] args) {
        java.util.Scanner scanner = new java.util.Scanner(System.in);
        int size = scanner.nextInt();
        int[][] arr = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                arr[i][j] = scanner.nextInt();
            }
        }
        findSubSumOfMat(arr);
    }

    public static void findSubSumOfMat(int matrix[][]) {
        if (matrix == null || matrix.length == 0)
            return;
        int max = 0;
        int cols = matrix[0].length;
        int rows = matrix.length;
        for (int row = 0; row < rows; row++) {//遍历所有行
            int subMat[] = new int[cols];
            for (int subRow = row; subRow < rows; subRow++) {//子行
                //遍历每一行的所有的子行情况
                for (int k = 0; k < cols; k++) {//子列
                    //将每子行 利用子数组的最大和
                    subMat[k] += matrix[subRow][k];
                }
                //求数组的子数组和最大值
                max = Math.max(maxSum(subMat), max);
            }
        }
        System.out.println(max);
    }

    /**
     * 计算子数组的最大和
     *
     * @param arr
     * @return
     */
    public static int maxSum(int arr[]) {
        int max = arr[0];
        int iMax = 0;//当前最大值
        for (int i = 0; i < arr.length; i++) {
            if (iMax <= 0) {
                iMax = arr[i];
            } else {
                iMax += arr[i];
            }
            max = Math.max(iMax, max);
        }
        return max;
    }
}
